package daily;

import java.util.Arrays;
import java.util.Stack;

public class Solution3243 {
    public static void main(String[] args) {
        Solution3243 solution = new Solution3243();
        System.out.println(solution.robotWithString("zza"));
        System.out.println(solution.robotWithString("bydizfve"));
    }
    public String robotWithString(String s) {
        char[] ch = s.toCharArray();
        // 使用后缀和统计[i, size-1]范围内最小字符所在位置
        int[] index = new int[ch.length];
        char minChar = ch[ch.length-1];
        int minIndex = ch.length - 1;
        for (int i = ch.length - 1; i >= 0; i --) {
            if (ch[i] <= minChar) {
                minIndex = i;
                minChar = ch[minIndex];
            }
            index[i] = minIndex;
        }

        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while(i < ch.length) {
            int right = index[i];
            String subString = s.substring(i, right+1);
            StringBuilder reverse = new StringBuilder(subString).reverse();
            sb.append(reverse.toString());
            i = right+1;
        }
        return sb.toString();
    }
}
